package 数据结构和算法入门计划8月开始;
// https://leetcode-cn.com/problems/fibonacci-number/
public class 斐波那契数5090819 {
    class Solution {

        public int fib(int n) {
            if(n==0) return 0;
            if(n<=2) return 1;
            return fib(n-1)+fib(n-2);
        }


            // public int fib(int n) {
            //     if(n==0) return 0;
            //     if(n<=2) return 1;
            //     return fib(n-1)+fib(n-2);
            // }

            // public int fib1(int n){
            //     if(n==0)return 0;
            //     int a=1;int  b=1;
            //     for(int i=2;i<n;i++){
            //         b=a+b;
            //         a=b-a;
            //     }
            //     return b;
            // }

            public int fib2(int n){
                if(n==0) return 0;
                if(n==1) return 1;
                int a=0,b=1,c=0;
                for(int i=1;i<n;i++){
                    c=a+b;
                    a=b;
                    b=c;
                }
                return c;
            }



    }
}
